//
// Created by dengspc on 2019/1/25.
//

#ifndef INC_010_ALGORITHM_BST_H
#define INC_010_ALGORITHM_BST_H
#include <iostream>
#include <cstring>
#include <queue>
#include <cassert>

#include "TestBinarySearchTreeHelper.h"
using namespace std;
using namespace TestBinarySearchTreeHelper;

template <typename Key,typename Value>
class BST:public SearchTree<Key,Value>{
private:
    struct Node{
        Key key;
        Value value;
        Node* left;
        Node* right;
        int N;

        Node(Key key,Value value){
            this->key=key;
            this->value=value;
            this->left=this->right=NULL;
            N=1;
        }

        Node(const Node* node){
            this->key=node->key;
            this->value=node->value;
            this->left=this->right=NULL;
            this->N=node->N;
        }
    };
    Node* root;

    /**
     * 插入以node节点为根的二叉树
     * @param node
     * @param key
     * @param value
     * @return
     */
    Node* _put(Node *node, Key key, Value value){
        if(node == NULL){
            node = new Node(key,value);
        }
        if(node->key==key){
            node->value=value;
        }else if(node->key>key){
            node->left = _put(node->left,key,value);
        }else{
            node->right = _put(node->right,key,value);
        }
        node->N =1+size(node->left)+size(node->right);
        return node;
    }

    /**
     *
     * @param node
     * @param key
     * @param value
     * @return
     */
    Node* _putWithOutRecursion(Node *node, Key key, Value value){
        if(node == NULL){
            node = new Node(key,value);
        }
        Node* n = node;
        Node* pre = NULL;
        bool isright = false;
        while(n!=NULL) {
            if(n->key==key){
                n->value=value;
                break;
            }else if(n->key>key){
                pre = n;
                n = n->left;
                isright = false;
            }else{
                pre = n;
                isright = true;
                n = n->right;
            }
        }
        if(n == NULL){
            n = new Node(key,value);
        }
        if(pre !=NULL){
            if(isright){
                pre->right = n;
            }else{
                pre->left=n;
            }
        }
        return node;
    }

    /**
     *
     * @param node
     * @param key
     * @return
     */
    bool _contain(Node * node, Key key){
        if(node == NULL)
            return false;
        if(node->key==key){
            return true;
        }
        if(node->key>key){
            return _contain(node->left,key);
        }
        if(node->key<key){
            return _contain(node->right,key);
        }
    }

    /**
     *
     * @param node
     * @param key
     * @return
     */
    Value* _search(Node * node, Key key){
        if(node == NULL)
            return NULL;
        if(node->key==key){
            return &(node->value);
        }
        if(node->key>key){
            return _search(node->left,key);
        }
        if(node->key<key){
            return _search(node->right,key);
        }
        return NULL;
    }

    /**
     *
     * @param node
     */
    void _preOrder(Node * node){

        if(node != NULL){
            cout<<node->key<<" ";
            _preOrder(node->left);
            _preOrder(node->right);
        }
    }

    /**
     *
     * @param node
     */
    void _midOrder(Node * node){

        if(node != NULL){
            _midOrder(node->left);
            cout<<node->key<<" ";
            _midOrder(node->right);
        }
    }

    /**
     *
     * @param node
     */
    void _afterOrder(Node * node){

        if(node != NULL){
            _afterOrder(node->left);
            _afterOrder(node->right);
            cout<<node->key<<" ";
        }
    }

    void _destory(Node * node){

        if(node != NULL){
            _destory(node->left);
            _destory(node->right);

            delete node;
        }
    }


    Node* _minNum(Node* node){
        while(node->left){
            node = node->left;
        }
        return node;
    }


    Node*  _maxNum(Node* node){
        while(node->right){
            node = node->right;
        }
        return node;
    }


    Node* _removeMax(Node* node){
        if(node->right==NULL){
            Node* left = node->left;
            delete node;
            return left;
        }
        node->right = _removeMax(node->right);
        node->N--;
        return node;
    }


    Node* _removeMin(Node* node){
        if(node->left==NULL){
            Node* right = node->right;
            delete node;
            return right;
        }
        node->left = _removeMin(node->left);
        node->N--;
        return node;
    }

    Node* _remove(Node* node, Key key){
        if(node==NULL){
            return NULL;
        }

        if(node->key>key){
            node->left = _remove(node->left,key);
            node->N = 1+size(node->left)+size(node->right);
            return node;
        }else if(node->key<key){
            node->right = _remove(node->right,key);
            node->N = 1+size(node->left)+size(node->right);
            return node;
        }else{
            if(node->left==NULL){
                Node* right = node->right;
                delete node;
                return right;
            }else if(node->right==NULL){
                Node* left = node->left;
                delete node;
                return left;
            }
            Node* newNode = new Node(_minNum(node->right));
            newNode->left=node->left;
            newNode->right=_removeMin(node->right);
            delete node;
            newNode->N = 1+size(newNode->left)+size(newNode->right);
            return newNode;
        }

    }

    int _rank(Node* node, Key key){
        int rank = 0;
        while(node != NULL){
            int leftN = node->left==NULL?0:node->left->N;
            if(node->key==key){
                return rank+leftN;
            }else if(node->key<key){
                rank+=leftN+1;
                node=node->right;
            }else{
                node=node->left;
            }
        }
        return rank;
    }

    /**
     *
     * @param node 当前节点
     * @param preRank 以node为根节点的树中最小节点的排名
     * @param select
     * @return
     */
    Node* _select(Node* node,int preRank,int select){
        int curentRank = (node->left==NULL?0:node->left->N)+preRank;
        if(select==curentRank){
            return node;
        }else if(select>curentRank){
            return _select(node->right,curentRank+1,select);
        }else{
            return _select(node->left,preRank,select);
        }
    }

    /**
     *
     * @param node
     * @param key
     * @return
     */
    Node* _floor(Node* node,Key key){
        if(node == NULL){
            return NULL;
        }
        if(node->key == key){
            return node;
        }else if(node->key>key){
            return _floor(node->left,key);
        }else{
            Node* n = _floor(node->right,key);
            return n==NULL?node:n;
        }
    }

    /**
 *
 * @param node
 * @param key
 * @return
 */
    Node* _ceiling(Node* node,Key key){
        if(node == NULL){
            return NULL;
        }
        if(node->key == key){
            return node;
        }else if(node->key<key){
            return _ceiling(node->right,key);
        }else{
            Node* n = _ceiling(node->left,key);
            return n==NULL?node:n;
        }
    }

    bool _isBST(Node* node, Key low, Key high){
        if(node == NULL) return true;
        if(low!=NULL && node->key<=low) return false;
        if(high!=NULL && node->key>=high) return false;
        return _isBST(node->left,low,node->key) && _isBST(node->right,node->key,high);
    }

    bool _isSizeConsistent(Node* node){
        if(node == NULL) return true;
        if(node->N!=1+size(node->left)+size(node->right))
            return false;
        return _isSizeConsistent(node->right) && _isSizeConsistent(node->left);
    }

    int size(Node* node){
        if(node==NULL) return 0;
        return node->N;
    }
public:
    BST(){
        root= NULL;
    }
    ~BST(){
        destory();
    }

    int size(){
        return isEmpty()?0:root->N;
    }
    bool isEmpty(){
        return root == NULL;
    }

    void put(Key key, Value value){
        root = _put(root,key,value);
    }

    bool coutain(Key key){
        return _coutain(root,key);
    }

    Value* search(Key key){
        return _search(root,key);
    }

    void preOrder(){
        _preOrder(root);
        cout<<endl;
    }

    void midOrder(){
        _midOrder(root);
        cout<<endl;
    }

    void afterOrder(){
        _afterOrder(root);
        cout<<endl;
    }

    void destory(){
        _destory(root);
    }

    void levelOrder(){
        queue<Node*> queue1;
        queue1.push(root);
        while(!queue1.empty()){
            Node* node = queue1.front();
            queue1.pop();
            cout<<node->key<<" ";
            if(node->left)
                queue1.push(node->left);
            if(node->right)
                queue1.push(node->right);
        }
        cout<<endl;
    }

    Key minNum(){
        assert(root!=NULL);
        Node* node = _minNum(root);
        return node->key;
    }

    Key maxNum(){
        assert(root!=NULL);
        Node* node = _maxNum(root);
        return node->key;
    }

    void removeMin(){
        if(root)
            root =  _removeMin(root);
    }

    void removeMax(){
        if(root)
            root =  _removeMax(root);
    }

    void remove(Key key){
        root = _remove(root,key);
    }

    Key* select(int select){
        assert(root!=NULL);
        assert(select>=0 && select<root->N);
        Node* node = _select(root,0,select);
        return &(node->key);
    }

    //小于key的键数量
    int rank(Key key){
        return _rank(root,key);
    }

    //小于等于key的最大值
    Key* floor(Key key){
        Node* node = _floor(root,key);
        return &(node->key);
    }

    //大于等于key的最小值
    Key* ceiling(Key key){
        Node* node = _ceiling(root,key);
        return &(node->key);
    }

    bool check(){
        bool ispassed = true;
        if(!isBST()){
            ispassed = false;
            cout<<" isBST = false"<<endl;
        }
        if(!isSizeConsistent()) {
            ispassed = false;
            cout << " isSizeConsistent = false" << endl;
        }
        if(!isRankConsistent()) {
            ispassed = false;
            cout << " isRankConsistent = false" << endl;
        }
        return ispassed;
    }

    bool isBST(){
        return _isBST(root,NULL,NULL);
    }

    bool isSizeConsistent(){
        return _isSizeConsistent(root);
    }

    bool isRankConsistent() {
        for (int i = 0; i < size(); i++)
            if (i != rank(*select(i))) return false;
        return true;
    }
};
//int main() {
//    BST<int,string> bst;
//    bst.insert(8,"4");
//    bst.insert(4,"2");
//    bst.insert(12,"6");
//    bst.insert(2,"1");
//    bst.insert(6,"3");
//    bst.insert(10,"5");
//    bst.insert(14,"7");
//    bst.insert(16,"8");
//
////    bst.preOrder();
////    bst.midOrder();
////    bst.afterOrder();
////    bst.levelOrder();
////
////    cout<<bst.minNum()<<endl;
////    cout<<bst.maxNum()<<endl;
////
////    bst.removeMax();
////    bst.levelOrder();
////    bst.removeMin();
////    bst.levelOrder();
////    bst.midOrder();
////    bst.remove(7);
////    bst.midOrder()
////    cout<<bst.rank(-1)<<endl;
////    cout<<*bst.select(7)<<endl;
//    int *fl = bst.floor(5);
//    cout<<(fl==NULL?-1:*fl)<<endl;
//    int *cl = bst.ceiling(5);
//    cout<<(cl==NULL?-1:*cl)<<endl;
//    return 0;
//}
#endif //INC_010_ALGORITHM_BST_H
